class NSPACE

Definition (space-bounded computation)

Let $S : \mathbb{N} \to \mathbb{N}$ and $L \in \{0,1\}^*$. Say that language $L \in \mathbf{NSPACE}(s(n))$ if there is a NDTM $M$ deciding $L$ that never uses more than $c \cdot s(n)$ nonblank tape locations on length $n$ inputs, for constant $c$, regardless of its nondeterministic choices.

Notes

• compare SPACE, the deterministic version

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 78-79.